package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/10.<br><br>
 *
 * 简单：二叉树的直径
 */
public class Topic543 {

    public static void main(String[] args) {
        Topic543 instance = new Topic543();

        List<Integer> list = Arrays.asList(1,2,3,4,5);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.diameterOfBinaryTree(root));

        instance.max = 0;
        list = Arrays.asList(1,2);
        root = Util.createTree(list);
        System.out.println(instance.diameterOfBinaryTree(root));
    }

    private int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;
    }
}
